A content addressable memory (CAM) is a memory device that accelerates any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks. Cams provide benefits over other memory search algorithms by simultaneously comparing the desired information (i.e., data input to the device or in the comparand register) against the entire list of pre-stored entries. As a result of their unique searching algorithm, CAM devices are frequently employed in network equipment, particularly routers and switches, computer systems and other devices that require rapid content searching.
In order to perform a memory search in the above-identified manner, Cams are organized differently than other memory devices (e.g., random access memory (RAM), dynamic RAM (DRAM), etc.). For example, data is stored in a RAM in a particular location, called an address. During a memory search on a RAM, the user supplies the address and gets back the data stored in that address (location).
In a CAM, however, data is stored in locations in a somewhat random fashion. The locations can be selected by an address, or the data can be written into a first empty memory location. Once information is stored in a memory location, it is found doing a memory search by comparing every bit in any memory location with every bit of data in a comparand register circuit. When the content stored in the CAM memory location does not match the data placed in the comparand register, the local match detect circuit associated with the CAM memory location returns a no-match indication. When the content stored in the CAM memory location matches the data placed in the comparand register, the local match detect circuit associated with the CAM memory location returns a match indication. If one or more of the local match detect circuits return a match indication then the CAM device outputs a match indication. If no local match detect circuits return a match indication then the CAM device outputs a no-match indication. In addition, if a match is found then the CAM returns the identification of the address location in which the matching data is stored (or one of the address locations in which matching data was stored if more than one memory location contained matching data). Thus, with a CAM, the user supplies the data and gets back an indication of an address where a matching data is stored in the memory.
It is conventional for Cams to perform the matching process described above in parallel, using one comparator circuit for every bit in the comparand. The present invention, conversely, horizontally shifts all of the bits in the comparand through the same comparator circuit. Doing so results in significant savings in logic circuitry, depending on the size of the comparand.
Also, during any particular search, more than one of match lines may indicate a match. This is because, as stated, the comparand can contain “wild-card” or “don't-care” conditions. In those conditions where a word with 100% matching bits does not exist, the present invention determines the memory words with the highest percentage of matching bits.